Improved Approximations for Guarding 1.5-Dimensional Terrains

We present a 4-approximation algorithm for the problem of placing the fewest guards on a 1.5D terrain so that every point of the terrain is seen by at least one guard. This improves on the previous best approximation factor of 5 (see King in Proceedings of the 13th Latin American Symposium on Theoretical Informatics, pp. 629–640, 2006). Unlike most of the previous techniques, our method is based on rounding the linear programming relaxation of the corresponding covering problem. Besides the simplicity of the analysis, which mainly relies on decomposing the constraint matrix of the LP into totally balanced matrices, our algorithm, unlike previous work, generalizes to the weighted and partial versions of the basic problem.     

Face Detection: A Survey

In this paper we present a comprehensive and critical survey of face detection algorithms. Face detection is a necessary first-step in face recognition systems, with the purpose of localizing and extracting the face region from the background. It also has several applications in areas such as content-based image retrieval, video coding, video conferencing, crowd surveillance, and intelligent human–computer interfaces. However, it was not until recently that the face detection problem received considerable attention among researchers. The human face is a dynamic object and has a high degree of variability in its apperance, which makes face detection a difficult problem in computer vision. A wide variety of techniques have been proposed, ranging from simple edge-based algorithms to composite high-level approaches utilizing advanced pattern recognition methods. The algorithms presented in this paper are classified as either feature-based or image-based and are discussed in terms of their technical approach and performance. Due to the lack of standardized tests, we do not provide a comprehensive comparative evaluation, but in cases where results are reported on common datasets, comparisons are presented. We also give a presentation of some proposed applications and possible application areas.     

An Introduction to Using XML for the Management of Laboratory Data

Extensible Markup Language (XML) and the XML Path Language (XPath) are introduced with software examples demonstrating how one can use them to write laboratory data management programs. Topics explored include XML document creation, manipulation, and searching. Programming examples make use of the Microsoft® XML Parser library and the Visual Basic programming language. The problem of managing microplate screening data is used as an illustration. Source code for all examples can be downloaded from http://www.labprogrammer.net.     

Real-time path planning in dynamic virtual environments using multiagent navigation graphs

We present a novel approach for efficient path planning and navigation of multiple virtual agents in complex dynamic scenes. We introduce a new data structure, Multi-agent Navigation Graph (MaNG), which is constructed using first- and second-order Voronoi diagrams. The MaNG is used to perform route planning and proximity computations for each agent in real time. Moreover, we use the path information and proximity relationships for local dynamics computation of each agent by extending a social force model [Helbing05]. We compute the MaNG using graphics hardware and present culling techniques to accelerate the computation. We also address undersampling issues and present techniques to improve the accuracy of our algorithm. Our algorithm is used for real-time multi-agent planning in pursuit-evasion, terrain exploration and crowd simulation scenarios consisting of hundreds of moving agents, each with a distinct goal.     

Dynamic programming for impulse controls

This paper describes the theory of feedback control in the class of inputs which allow delta-functions and their derivatives. It indicates a modification of dynamic programming techniques appropriate for such problems. Introduced are physically realizable bang-bang-type approximations of the “ideal” impulse-type solutions. These may also serve as “fast” feedback controls which solve the terminal control problem in arbitrary small time. Examples of damping high-order oscillations in finite time are presented.     

Staged self-assembly: nanomanufacture of arbitrary shapes with <Emphasis Type="Italic">O</Emphasis>(1) glues

We introduce staged self-assembly of Wang tiles, where tiles can be added dynamically in sequence and where intermediate constructions can be stored for later mixing. This model and its various constraints and performance measures are motivated by a practical nanofabrication scenario through protein-based bioengineering. Staging allows us to break through the traditional lower bounds in tile self-assembly by encoding the shape in the staging algorithm instead of the tiles. All of our results are based on the practical assumption that only a constant number of glues, and thus only a constant number of tiles, can be engineered. Under this assumption, traditional tile self-assembly cannot even manufacture an n × n square; in contrast, we show how staged assembly in theory enables manufacture of arbitrary shapes in a variety of precise formulations of the model.

How crystals that sense and respond to their environments could evolve

An enduring mystery in biology is how a physical entity simple enough to have arisen spontaneously could have evolved into the complex life seen on Earth today. Cairns-Smith has proposed that life might have originated in clays which stored genomes consisting of an arrangement of crystal monomers that was replicated during growth. While a clay genome is simple enough to have conceivably arisen spontaneously, it is not obvious how it might have produced more complex forms as a result of evolution. Here, we examine this possibility in the tile assembly model, a generalized model of crystal growth that has been used to study the self-assembly of DNA tiles. We describe hypothetical crystals for which evolution of complex crystal sequences is driven by the scarceness of resources required for growth. We show how, under certain circumstances, crystal growth that performs computation can predict which resources are abundant. In such cases, crystals executing programs that make these predictions most accurately will grow fastest. Since crystals can perform universal computation, the complexity of computation that can be used to optimize growth is unbounded. To the extent that lessons derived from the tile assembly model might be applicable to mineral crystals, our results suggest that resource scarcity could conceivably have provided the evolutionary pressures necessary to produce complex clay genomes that sense and respond to changes in their environment.

A Pedagogy of Play: Integrating Computer Games into the Writing Classroom

Traditional distinctions between work/play and classroom/gamespace create barriers to computer games’ integration into academic settings and the writing classroom in particular. For a writing class, the work/play distinction often relegates games to an object of analysis in which students critique the games but have little invested in the gameplay itself. After examining briefly how historical changes in education created these distinctions, we offer an alternative position that places play and gamespace within the realm of the classroom. In so doing, we open up a gap for computer game theory to inform the pedagogy that can be practiced in a writing classroom. We show one such example of game theory informing writing pedagogy—the theory of emergent gaming. We then offer an example of an enacted emergent pedagogy in which students play the massively multiplayer online role-playing game World of Warcraft throughout the term, composing self-determined, rhetorically focused writing projects informed by play and written for other game players.